Lowest common ancestor of deepest leaves [DFS]

Time: O(N); Space: O(H); medium

Given a rooted binary tree, return the lowest common ancestor of its deepest leaves.

Recall that:

• The node of a binary tree is a leaf if and only if it has no children

• The depth of the root of the tree is 0, and if the depth of a node is d, the depth of each of its children is d+1.

• The lowest common ancestor of a set S of nodes is the node A with the largest depth such that every node in S is in the subtree with root A.

Example 1:

  1
 / \
2   3

Input: root = {TreeNode} [1,2,3]

  1
 / \
2   3

Output: {TreeNode} [1,2,3]

Explanation:

• The deepest leaves are the nodes with values 2 and 3.

• The lowest common ancestor of these leaves is the node with value 1.

• The answer returned is a TreeNode object (not an array) with serialization “[1,2,3]”.

Example 2:

    1
   / \
  2   3
 /
4

Input: root = {TreeNode} [1,2,3,4]

4

Output: {TreeNode} [4]

Example 3:

    1
   / \
  2   3
 / \
4   5

Input: root = {TreeNode} [1,2,3,4,5]

  2
 / \
4   5

Output: {TreeNode} [2,4,5]

Constraints:

• The given tree will have between 1 and 1000 nodes.

• Each node of the tree will have a distinct value between 1 and 1000.

Hints:

1. Do a postorder traversal.

2. Then, if both subtrees contain a deepest leaf, you can mark this node as the answer (so far).

3. The final node marked will be the correct answer.

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

Auxiliary Tools

from graphviz import Graph

class TreeTasks(object):
    def visualize_tree(self, tree):
        def add_nodes_edges(tree, dot=None):
            # Create Graph (not Digraph) object
            if dot is None:
                dot = Graph()
                dot.node(name=str(tree), label=str(tree.val))
            # Add nodes
            if tree.left:
                dot.node(name=str(tree.left), label="."+str(tree.left.val))
                dot.edge(str(tree), str(tree.left))
                dot = add_nodes_edges(tree.left, dot=dot)
            if tree.right:
                dot.node(name=str(tree.right), label=str(tree.right.val)+".")
                dot.edge(str(tree), str(tree.right))
                dot = add_nodes_edges(tree.right, dot=dot)
            return dot
        # Add nodes recursively and create a list of edges
        dot = add_nodes_edges(tree)
        # Visualize the graph
        display(dot)
        return dot

1. Depth First Search

class Solution1(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def lcaDeepestLeaves(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        def lcaDeepestLeavesHelper(root):
            if not root:
                return 0, None

            d1, lca1 = lcaDeepestLeavesHelper(root.left)
            d2, lca2 = lcaDeepestLeavesHelper(root.right)

            if d1 > d2:
                return d1 + 1, lca1
            if d1 < d2:
                return d2 + 1, lca2
            return d1 + 1, root

        return lcaDeepestLeavesHelper(root)[1]

s = Solution1()

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
tree = s.lcaDeepestLeaves(root)
t = TreeTasks()
dot = t.visualize_tree(tree)

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.left = TreeNode(4)
tree = s.lcaDeepestLeaves(root)
t = TreeTasks()
dot = t.visualize_tree(tree)

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.left, root.left.right = TreeNode(4), TreeNode(5)
tree = s.lcaDeepestLeaves(root)
t = TreeTasks()
dot = t.visualize_tree(tree)

See also:

https://leetcode.com/problems/lowest-common-ancestor-of-deepest-leaves